package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 292. Nim游戏
 * @date 2025/3/11 12:14
 */
public class E292 {

    /**
     * <3>方法一：动态规划</3>
     *
     * @param n 盘子数
     * @return 是否能赢
     */
    public boolean canWinNim(int n) {
        if (n <= 3) return true;
        boolean[] dp = new boolean[n + 1];
        dp[1] = true;
        dp[2] = true;
        dp[3] = true;
        for (int i = 4; i <= n; i++) {
            // 前面三次有至少一次赢不了，则当前必赢
            dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
        }
        return dp[n];
    }

    /**
     * <3>方法二：数学推论</3>
     *
     * @param n 盘子数
     * @return 是否能赢
     */
    public boolean canWinNim1(int n) {
        return n % 4 != 0;
    }

    /**
     * <3>方法三将n % 4换成位运算</3>
     *
     * @param n 盘子数
     * @return 是否能赢
     */
    public boolean canWinNim2(int n) {
        return (n & 3) != 0;
    }
}
